#include <bits/stdc++.h>
using namespace std;

//KMP算法
class Solution {
public:
    void getNext(int *next, const string& s){
        int j = -1;
        next[0] = j;
        for(int i=1; i<s.size(); ++i){
            int t=0;
            //s[i]是新后缀 s[j+1]是新前缀
            while(j>=0 && s[i]!=s[j+1]){
                j = next[j];    //如果新后缀!=新前缀,则跳到上一个相同的前缀字母
            }
            if(s[i] == s[j+1]){ //捕捉第一个前缀=后缀的位置
                j++;    //记录next值
            }
            next[i] = j;
        }
    }
    int strStr(string haystack, string needle) {
        if(needle.size() == 0) return 0;
        vector<int> next(needle.size());
        getNext(&next[0], needle);
        int j=0;
        for(int i=0; i<haystack.size(); ++j){
            while(j>0 && haystack[i]!=needle[i]){
                j = next[j-1];  //跳转到needle中上一个与haystack[i]相同的位置
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == needle.size() ) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

int main(){
    Solution solution;
    int next[100];
    string s="aab";
    solution.getNext(next, s);
}